package com.example.javabasic.mianshi;

import com.example.javabasic.mianshi.fuzhulei.ListNode;

/**
 * 合并两个有序链表
 */
public class PaixuLianbiao {

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7, 9};
        int[] arr2 = {2, 4, 6, 8, 10};
        ListNode listNode = create(arr1);
        ListNode listNode1 = create(arr2);
//        ListNode merge = Merge(listNode1, listNode);
//        System.out.println(merge);
        ListNode digui = digui(listNode, listNode1);
        System.out.println(digui);
    }

    /**
     * 生成 链表
     *
     * @param arr
     * @return
     */
    public static ListNode create(int[] arr) {
        ListNode node = new ListNode(arr[0]);
        ListNode now = node;
        for (int i = 1; i < arr.length; i++) {
            now.next = new ListNode(arr[i]);
            now = now.next;
        }
        return node;
    }

    /**
     * 合并链表
     *
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode head = new ListNode(0);
        ListNode node = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                node.next = list1;
                list1 = list1.next;
            } else {
                node.next = list2;
                list2 = list2.next;
            }
            node = node.next;
        }
        if (list1 == null) {
            node.next = list2;
        }
        if (list2 == null) {
            node.next = list1;
        }
        return head.next;
    }

    /**递归*/
    public static ListNode digui(ListNode a,ListNode b){
        if(a == null){
            return b;
        }
        if(b == null){
            return a;
        }

        if(a.val>b.val){
            b.next =  digui(a,b.next);
            return b;
        }else{
            a.next = digui(a.next,b);
            return a;
        }
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode first = null;
        ListNode temp = first;
        //确定头结点
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        if (l1.val < l2.val) {
            temp = l1;
            l1 = l1.next;
        } else {
            temp = l2;
            l2 = l2.next;
        }

        for (; ; ) {
            if (l1 == null) {
                if (l2 != null) {
                    temp.next = l2;
                    return first;
                }
            } else {
                if (l2 == null) {
                    temp.next = l1;
                    return first;
                } else {
                    if (l1.val < l2.val) {
                        temp.next = l1;
                        l1 = l1.next;
                    } else {
                        temp.next = l2;
                        l2 = l2.next;
                    }
                }
            }
        }
    }

}
